package hash;

import java.util.NoSuchElementException;

/**
 * 基于开散列的哈希表的实现
 */
public class MyHashMap {
    private class Node{
        //对key求哈希运算
        int key;
        int value;
        //发生哈希碰撞时转链表用next属性存储它的下一个节点
        Node next;

        public Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    private int size;
    //默认哈希表的长度
    private static final int DEFAULT_CAPACITY=16;
    //默认负载因子
    private static final double LOAD_FACTOR=0.75;
    //取模数，用于取到key的索引
    private int M;
    //实际存储数据的数组
    private Node[] data;

    public MyHashMap() {
        this(DEFAULT_CAPACITY);
    }

    public MyHashMap(int initCap) {
        this.data=new Node[initCap];//可以从外部传入
        this.M=initCap;//initCap:长度，数组长度赋给取模数
    }
    public int hash(int key){
        return Math.abs(key)%M;
    }

    /**
     * 添加键值对key=value
     * @param key
     * @param value
     * @return
     */
    public int add(int key,int value){
        int index=hash(key);//对key取模，得到存储的索引
        //遍历索引对应链表，查看当前key是否已存在
        for(Node x=data[index];x!=null;x=x.next){
            if(x.key==key){
                //此时key已存在，更新value即可
                int oldValue=x.value;
                x.value=value;
                return oldValue;
            }
        }
        //此时key在哈希表中还不存在，新建节点头插在哈希表中
        Node node=new Node(key,value,data[index]);
        //最新链表的头节点要变为当前的node
        data[index]=node;
        size++;
        //添加一个新元素后，查看是否需要扩容
        if(size/LOAD_FACTOR>= data.length){
            resize();
        }
        return value;
    }
    /**
     * 查询key是否存在
     */
    public boolean containsKey(int key){
        int index=hash(key);
        //遍历index位置对应链表，看key是否存在
        for (Node x=data[index];x!=null;x=x.next){
            if(x.key==key){
                return true;
            }
        }
        return false;
    }
    /**
     * 查询val是否存在
     */
    public boolean containsValue(int value){
        //遍历整个哈希表
        for (int i = 0; i < size; i++) {
            //依次遍历每个数组元素对应链表
            for (Node x=data[i];x!=null;x=x.next){
                if(x.value==value){
                    return true;
                }
            }
        }
        return false;
    }
    /**
     * 删除key值对应节点
     * 返回待删除键值对对应的value
     */
    public int remove(int key){
        //头节点是否是待删除结点
        int index=hash(key);
        Node head=data[index];
        if(head.key==key){
            //头节点待删除
            int value= head.value;
            data[index]=head.next;
            head=head.next=null;
            size--;
            return value;
        }
        //当前链表头节点不是待删除节点
        Node prev=head;
        while (prev.next!=null){
            if(prev.next.key==key){
                //prev恰好是待删除节点的前驱
                Node cur=prev.next;
                int val=cur.value;
                prev.next=cur.next;
                cur.next=cur=null;
                size--;
                return val;
            }
            prev=prev.next;
        }
        //没有key节点，抛出异常
        throw new NoSuchElementException("no such key!remove error!");
    }
    /**
     * 哈希表的扩容
     */
    private void resize(){
        Node[] newData=new Node[data.length<<1];//长度*2
        //细节：扩容后的key对应的取模也有变化
        this.M= newData.length;
        //遍历原数组进行节点搬移
        for (int i = 0; i < data.length; i++) {
            if(data[i]!=null){
                //进行链表遍历
                for(Node x=data[i];x!=null;x=x.next){
                    //暂存后继节点
                    Node next=x.next;
                    //找到新数组索引
                    int newIndex=hash(x.key);
                    //头插
                    x.next=newData[newIndex];
                    newData[newIndex]=x;
                    x=next;
                }
            }else {
                continue;
            }
        }
        data=newData;
    }
}
